Library of sophisticated functions for analysis of nuclear spectra

In the paper we present compact library for analysis of nuclear spectra. The library consists of sophisticated functions for background elimination, smoothing, peak searching, deconvolution, and peak fitting. The functions can process one- and two-dimensional spectra. The software described in the paper comprises a number of conventional as well as newly developed methods needed to analyze experimental data.

Program summary

Program title: SpecAnalysLib 1.1Catalogue identifier: AEDZ_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEDZ_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 42 154No. of bytes in distributed program, including test data, etc.: 2 379 437Distribution format: tar.gzProgramming language: C++Computer: Pentium 3 PC 2.4 GHz or higher, Borland C++ Builder v. 6. A precompiled Windows version is included in the distribution packageOperating system: Windows 32 bit versionsRAM: 10 MBWord size: 32 bitsClassification: 17.6Nature of problem: The demand for advanced highly effective experimental data analysis functions is enormous. The library package represents one approach to give the physicists the possibility to use the advanced routines simply by calling them from their own programs. SpecAnalysLib is a collection of functions for analysis of one- and two-parameter γ-ray spectra, but they can be used for other types of data as well. The library consists of sophisticated functions for background elimination, smoothing, peak searching, deconvolution, and peak fitting.Solution method: The algorithms of background estimation are based on Sensitive Non-linear Iterative Peak (SNIP) clipping algorithm. The smoothing algorithms are based on the convolution of the original data with several types of filters and algorithms based on discrete Markov chains. The peak searching algorithms use the smoothed second differences and they can search for peaks of general form. The deconvolution (decomposition - unfolding) functions use the Gold iterative algorithm, its improved high resolution version and Richardson-Lucy algorithm. In the algorithms of peak fitting we have implemented two approaches. The first one is based on the algorithm without matrix inversion - AWMI algorithm. It allows it to fit large blocks of data and large number of parameters. The other one is based on the calculation of the system of linear equations using Stiefel-Hestens method. It converges faster than the AWMI, however it is not suitable for fitting large number of parameters.Restrictions: Dimensionality of the analyzed data is limited to two.Unusual features: Dynamically loadable library (DLL) of processing functions users can call from their own programs.Running time: Most processing routines execute interactively or in a few seconds. Computationally intensive routines (deconvolution, fitting) execute longer, depending on the number of iterations specified and volume of the processed data.     

On the decoding of binary cyclic codes with the Newton identities

We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a case-by-case basis. It is tempting to automate these computations, using elimination theory and Gröbner bases.Thus, we study in this paper the properties of the system defined by the Newton identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated with this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas.Then we consider the so-called online Gröbner basis decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred).     

基于翻译规则的统计机器翻译

扩展HMM模型可以解决词语对齐结果与句法约束冲突,从而更好地进行词语对齐。在短语对齐基础上利 用目标语言的短语结构树抽取翻译规则。采用扩展CYK算法CYKA+作为系统的解码器,该算法可以处理非乔姆 斯基范式的翻译规则;采用两轮解码算法在解码过程中整合语言模型。实验表明,与传统词语对齐模型相比,改进的 HMM词语对齐模型具有更高的对齐准确率,并且翻译结果的BLEU评测得分更高。采用翻译规则的系统在不同数 据集上具有更稳定的翻译结果。两轮解码算法与立方剪枝算法具有相近的解码质量,但前者解码速度更快。     

Real-time approximation of molecular interaction interfaces based on hierarchical space decomposition

The interaction interface between two molecules can be represented as a bisector surface equidistant from the two sets of spheres of varying radii representing atoms. We recursively divide a box containing both sphere-sets into uniform pairs of sub-boxes. The distance from each new box to each sphere-set is conservatively approximated by an interval, and the number of sphere-box computations is greatly reduced by pre-partitioning each sphere-set using a kd-tree. The subdivision terminates at a specified resolution, creating a box partition (BP) tree. A piecewise linear approximation of the bisector surface is then obtained by traversing the leaves of the BP tree and connecting points equidistant from the sphere-sets. In 124 experiments with up to 16,728 spheres, a bisector surface with a resolution of 1/2⁴ of the original bounding box was obtained in 28.8 ms on average.     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Input-output properties of the Page-Hinkley detector

We consider the stochastic input-output properties of a simple non-linear dynamical system, the so-called Page-Hinkley detector, playing a key role in change detection, and also in queuing theory. We show that for L-mixing inputs with negative expectation the output process of this system is L-mixing. The result is applied to get an upper bound for the false alarm rate. The proof is then adapted to get a similar result for the case of random i.i.d. inputs. Possible extensions and open problems are given in the discussion.     

Design of experiments for bivariate binary responses modelled by Copula functions

Optimal design for generalized linear models has primarily focused on univariate data. Often experiments are performed that have multiple dependent responses described by regression type models, and it is of interest and of value to design the experiment for all these responses. This requires a multivariate distribution underlying a pre-chosen model for the data. Here, we consider the design of experiments for bivariate binary data which are dependent. We explore Copula functions which provide a rich and flexible class of structures to derive joint distributions for bivariate binary data. We present methods for deriving optimal experimental designs for dependent bivariate binary data using Copulas, and demonstrate that, by including the dependence between responses in the design process, more efficient parameter estimates are obtained than by the usual practice of simply designing for a single variable only. Further, we investigate the robustness of designs with respect to initial parameter estimates and Copula function, and also show the performance of compound criteria within this bivariate binary setting.     

Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

Rectangle packing with additional restrictions

We formulate a generalization of the NP-complete rectangle packing problem by parameterizing it in terms of packing density, the ratio of rectangle areas, and the aspect ratio of individual rectangles. Then we show that almost all restrictions of this problem remain NP-complete and identify some cases where the answer to the decision problem can be found in constant time.